package algorithm.t202110;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/26 9:05
 * @description :2道
 * 月是故乡明。
 * persevere to last.
 * 2021.10.26
 */
public class t20211026 {

    //496.下一个更大元素 | Next Greater Number 【单调栈】
    static public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if (nums2 == null) {
            return new int[]{-1};
        }


        int[] res = new int[nums1.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = -1;
        }

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == nums1[i]) {//拿到目标值

                    while (j + 1 < nums2.length) {//开始向右边搜索
                        if (nums2[j + 1] > nums1[i]) {
                            res[i] = nums2[j + 1];
                            break;
                        }
                        j++;
                    }

                }

            }

        }

        return res;
    }

    static public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        if (nums2 == null) {
            return new int[]{-1};
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[nums1.length];

        for (int i = 0; i < nums2.length; i++) {
            //遍历nums2，得到nums2中元素的关系映射，然后num1就可以直接获取关系结果

            if (stack.isEmpty()) {
                //直接入栈
                stack.push(nums2[i]);
            } else if (nums2[i] > stack.peek()) {//当前遍历到的元素大于栈顶元素
                Integer pop = stack.pop();//弹出栈顶元素
                map.put(pop, nums2[i]);//记录映射关系

                while (!stack.isEmpty()) {
                    if (nums2[i] > stack.peek()) {//说明之前栈顶的下一个元素依然小于当前元素，也就是当前元素是他们的【next greater number】
                        Integer pop2 = stack.pop();//弹出栈顶元素
                        map.put(pop2, nums2[i]);//记录映射关系
                    } else {
                        break;
                    }

                }
                //当栈为空或者遇到比当前元素大的元素，将当前元素入栈
                stack.push(nums2[i]);


            } else {//当前遍历到的元素小于栈顶元素
                //直接压栈
                stack.push(nums2[i]);
            }

        }

        for (int i = 0; i < res.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);

        }

        return res;
    }

    static public int[] nextGreaterElement3(int[] nums1, int[] nums2) {

        HashMap<Integer, Integer> map = new HashMap<>();
        LinkedList<Integer> stack = new LinkedList<>();

        //先将nums2中【next greater number】关系映射如哈希表
        for (int i = 0; i < nums2.length; i++) {

            while (!stack.isEmpty() && stack.peek() < nums2[i]) {//栈不为空并且栈顶元素小于当前元素，才会进行映射关系处理
                int temp = stack.pop();
                map.put(temp, nums2[i]);
            }

            //若栈为空，或者栈顶元素大于当前元素，则入栈
            stack.push(nums2[i]);

        }

        //通过映射关系来获取答案
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }


    //82.删除排序链表中的重复元素
    static public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        if (head.val != head.next.val) {//保留head
            head.next = deleteDuplicates(head.next);
        } else {//程序走到这表示：head是一定要丢弃的，至于head后面的元素要丢弃多少，就要用递归才知道
            ListNode temp = head.next.next;
            while (temp != null && temp.val == head.val) {
                temp = temp.next;
            }

            return deleteDuplicates(temp);
        }

        return head;
    }

    static public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        HashMap<Integer, Integer> map = new HashMap<>();//用于记录链表中节点出现的次数

        //遍历链表
        ListNode temp = head;
        while (true) {
            if (temp.next == null) {
                map.put(temp.val, map.getOrDefault(temp.val, 0) + 1);
                break;
            }
            map.put(temp.val, map.getOrDefault(temp.val, 0) + 1);
            temp = temp.next;

        }


        int num = 0;
        //通过哈希表来组装链表
        Set<Integer> keySet = map.keySet();
        ArrayList<Integer> arr = new ArrayList<>();
        for (Integer integer : keySet) {
            if (map.get(integer) == 1) {
                arr.add(integer);
            }

        }
        ListNode dummy = new ListNode(-1);
        temp = dummy;

        Collections.sort(arr);
        for (int i : arr) {//组装一个新链表
            ListNode node = new ListNode(i);
            temp.next = node;
            temp = temp.next;

        }

        return dummy.next;
    }

    static public ListNode deleteDuplicates3(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(-1);//定义一个哑节点
        dummy.next = head;

        //双指针
        ListNode one = dummy;//指向哑节点
        ListNode two = head;//指向头节点

        while (true) {
            if (one.next == null || two.next == null || two == null || one == null) {
                //TODO
                break;
            }

            if (one.next.val != two.next.val) {
                one = one.next;
                two = two.next;
            } else {
                while (two.next != null && one.next.val == two.next.val) {
                    two = two.next;
                }
                one.next = two.next;
                two = two.next;

            }

        }

        return dummy.next;
    }




    static public int  test(String str){
        int count=0;
        for (int i = 0; i < str.length(); i++) {

            if(str.charAt(i)=='(' && i+1<str.length() && str.charAt(i+1)==')'){
                count+=2;
            }
        }
        return count;
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(4);
        ListNode node6 = new ListNode(5);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        node4.next = node5;
        node5.next = node6;

        deleteDuplicates2(head);
        System.out.println("括号？？"+test("()(()"));

    }

}

